#include <stdio.h>
#include <malloc.h>
/* tutaj taka mała flaga preprocesora, jak ją zakomentujecie to fragmenty kodu zawarte pomiędzy
#ifdef DEBUG a #endif nie będą kompilowane, czyli nie będą wyświetlane komunikaty pomocnicze */
#define DEBUG

struct ts_list //struktura opisująca element listy
{
      int key; //wartość
      ts_list *prev,*next; //wskaźniki na poprzedni i następny element listy
      } *head=NULL, *x=NULL; //head to nasz pierwszy element, x to jakiœtam pomocniczy

ts_list *push(ts_list *head,ts_list *x)
{
        x->next=head; //dodajemy nasz element na początku listy
        x->prev=NULL; // będzie on naszym nowym początkiem, dlatego pole prev nie może wskazywać na nic
        if(head!=NULL) head->prev=x; //jeżeli lista wcześniej nie była pusta, to dobrze by było ustawić wskazanie prev starej głowie na tą nową
        return x;
}

void list(ts_list *head) // wersja rekurencyjna
{
     if(head==NULL)
     {
         #ifdef DEBUG
         printf("\nlist()::Nie ma listy!"); // no nie ma, i chuj
         #endif
         return;
         }
     #ifdef DEBUG
     if(head->prev==NULL) printf("\nlist():: ");
     #endif
     printf("%i ",head->key);
     return head->next==NULL ? (void)NULL : list(head->next); // albo inaczej: if(head->next==NULL) return; else list(head->next);
}

ts_list *tail(ts_list *head)
{
while(head->next) head=head->next; //lecimy po liście dopuki nie trafimy na koniec tj na element którego wskaźnik next pokazuje na NULL
return head;
}

ts_list *search(ts_list *head, int k)//szukamy czegoś
{
        if(head==NULL)
        {
            #ifdef DEBUG
            printf("\nsearch(%i)::Nie ma listy!",k);
            #endif
            return head;
        }
        while(head!=NULL && head->key!=k)//dopuki nie trafimy na koniec listy lub na szukany element
        head=head->next; //przesuwamy się do przodu po liście
        #ifdef DEBUG
        if(head==NULL) printf("\nsearch(%i)::Brak elementu na liscie!",k);
        else
        printf("\nsearch(%i)::znaleziono",k);
        #endif
        return head;
}

ts_list *eject(ts_list *head, ts_list *x) //usuwanie elementu(x) z listy
{
        if(head==NULL)
        {
            #ifdef DEBUG
            printf("\neject(#)::Nie ma listy!");
            #endif
            return head;
        }
        else if(x==NULL) //ciężko jest usunąć "nic"
        {
            #ifdef DEBUG
            printf("\neject(#)::Nie mozna usunac NULL!");
            #endif
            return head;
        }
        else if(x->prev) // jeżeli usuwany element miał wskazanie na jakiś poprzedni to wiemy że na pewno nie była to głowa listy
        {
              if(x->next) // dodatkowo jeżeli wiemy że miał wskazanie na jakiś następny element to nie był to koniec listy
              { //tutaj troszkę zawiłości
                    x->prev->next=x->next; //wskazanie na element następny elementu poprzedającego usuwany ustawiamy na wskazanie elementu po tym usuwanym
                    x->next->prev=x->prev; //wskazanie na element poprzedni elementu następnego po usuwanym ustawiamy na wskazanie elementu poprzedzającego ten usuwany
              }
              else //jednak się okazało ze trafiliśmy na koniec listy
                    x->prev->next=NULL; //wskazanie na element następny elementu poprzedzającego usuwany ustawiamy na NULL, to będzie nasz nowy koniec listy
        }
        else if(x->next)//tutaj wiemy że element to głowa listy
        {
              x->next->prev=NULL; // ustawiamy nową głowę
              head=x->next;
        }
        else //nie ma innej możliwości, trafiliśmy na głowę listy
              head=NULL;
        #ifdef DEBUG
        printf("\neject(%i)::ok",x->key);
        #endif
        free(x); //zwalniamy pamięć
        return head;
}


ts_list *snd(ts_list *head) // drugi element listy, przy założeniu że numerujemy od 0
{
    return head==NULL ? NULL : head->next;
}

int main()
{
  const int n=4;
  for(int i=1;i<=n;i++) // alokujemy pamięć dla naszej listy (dla n elementów)
  {
          x=(ts_list *)malloc(sizeof(ts_list)); //tutaj alokujemy pamięć dla jednego elementu
          if(x==NULL) printf("\nBlad alokacji pamieci"); //ups
          else
          {
              x->key=i; // w pola wartości wstawiamy nasz iterator pętli (chyba nie chcemy mieć listy ze śmieciami?)
              x->prev=x->next=NULL;
              head=push(head,x); // ostatecznie dodajemy element do listy
          }
  }
  //tutaj mały eksperyment
  list(head);
  x=search(head,1);
  head=eject(head,x);
  list(head);
  x=search(head,2);
  head=eject(head,x);
  list(head);
  x=search(head,248728947); //chyba nie ma czegoś takiego w liście?
  head=eject(head,x);
  list(head);
  x=search(head,3);
  head=eject(head,x);
  list(head);
  x=search(head,3);
  head=eject(head,x);
  list(head);

  return 0;
}
